#include "BigInt.h"
#include <cstring>
#include <cstdio>
#include <iomanip>
using namespace std;

BigInt::BigInt()
{
	memset(coeff, 0, sizeof(coeff));
	length = 1;
}

void BigInt::fromString(const char* str10)
{
	memset(coeff, 0, sizeof(coeff));

	int len = strlen(str10);
	char nextDigitStr[5] = {'\0'};
	int i = 0; // i-th digit
	int pos = len - BASE_LOG10;
	while (pos >= 0)
	{
		strncpy(nextDigitStr, str10 + pos, BASE_LOG10);
		sscanf(nextDigitStr, "%d", &coeff[i]);
		++i;
		pos -= BASE_LOG10;
	}
	
	if (pos < 0)
	{
		pos += BASE_LOG10;
		strncpy(nextDigitStr, str10, pos);
		nextDigitStr[pos] = '\0';
		sscanf(nextDigitStr, "%d", &coeff[i]);
		++i;
	}

	length = i;
	while (length > 0 && coeff[length-1] == 0)
		--length;
}

BigInt::BigInt(const char* str10)
{
	this->fromString(str10);
}

std::ostream& operator << (std::ostream& os, const BigInt& b)
{
	char oldFillChar = os.fill('0');

	int i = b.length - 1;
	os << b[i];

	for (--i; i >= 0; --i)
		os << setw(BigInt::BASE_LOG10) << b[i];

	os.fill(oldFillChar);
	return os;
}

std::istream& operator >> (std::istream& is, BigInt& b)
{
	char str10[BigInt::MAX_LENGTH + 10];
	is >> str10;
	b.fromString(str10);
	return is;
}

BigInt::BigInt(long long int a)
{
	char str10[sizeof(a) * 4];
	sprintf(str10, "%lld", a);
	this->fromString(str10);
}

BigInt BigInt::operator + (const BigInt& b) const
{
	const BigInt& a = *this;
	BigInt c; // c = a + b

	DigitType carry = 0;

	int i, nextDigit;
	for (i = 0; i < max(a.length, b.length); ++i)
	{
		nextDigit = a[i] + b[i] + carry;
		if (nextDigit >= BASE)
		{
			carry = 1;
			c[i] = nextDigit - BASE;
		}
		else
		{
			carry = 0;
			c[i] = nextDigit;
		}
		
	}
	
	c.length = i;

	if (carry)
	{
		c[i] = carry;
		++c.length;
	}

	return c;
}

BigInt BigInt::operator - (const BigInt& b) const
{
	if (*this < b)
	{
		cerr << "Operator - : left operand less than the right one. Negative numbers are not supported yet." << endl;
		exit(5);
	}
	
	const BigInt& a = *this;
	BigInt c; // c = a - b

	DigitType carry = 0;

	int i, nextDigit;
	for (i = 0; i < a.length; ++i)
	{
		nextDigit = a[i] - b[i] + carry;

		if (nextDigit < 0)
		{
			carry = -1;
			c[i] = nextDigit + BASE;
		}
		else
		{
			carry = 0;
			c[i] = nextDigit;
		}
	}
	
	c.length = a.length;
	while (c.length > 0 && c[c.length - 1] == 0)
		--c.length;

	return c;
}

BigInt BigInt::operator * (const ShortType b) const
{
	int i, temp;
	const BigInt& a = *this;
	BigInt c;
	DigitType carry = 0;

	for (i = 0; i < a.length; ++i)
	{
		temp = a[i]*b + carry;
		carry = temp/BASE;
		c[i] = temp - carry*BASE;
	}

	c.length = i;

	if (carry)
	{
		c[i] = carry;
		c.length = i + 1;
	}

	// this is important when c is 0
	while (c.length > 0 && c[c.length - 1] == 0)
		--c.length;

	return c;
}

BigInt BigInt::operator * (const BigInt& b) const
{
	BigInt c;
	const BigInt& a = *this; // c = a * b

	int i, j;
	int temp, carry;

	for (i = 0; i < a.length; ++i)
	{
		carry = 0;

		for (j = 0; j < b.length; ++j)
		{
			temp = a[i] * b[j] + c[i+j] + carry;
			carry = temp/BASE;
			c[i+j] = temp - carry*BASE;
		}
		c[i+j] = carry;
	}

	c.length = a.length + b.length;
	while (c.length > 0 && c[c.length - 1] == 0)
		--c.length;

	return c;
}


BigInt BigInt::operator / (const BigInt& b) const
{
	BigInt c;
	const BigInt& a = *this; // c = a * b

	if (a < b)
		return c;

	int i, j;
	BigInt r; // rest of division on the previous step
	BigInt temp, prod;
	DigitType ld, md, hd; // ld - lower digit, md - middle digit, hd - higher digit
	BigInt base = BASE;

	for (i = a.length - 1; i >= 0; --i)
	{
		temp = r*base + a[i];
		
		ld = 0, hd = BASE - 1;

		while (ld < hd)
		{
			md = (ld + hd)/2;
			
			prod = b * md;
			if (prod > temp)
				hd = md;
			else
			{
				ld = md;
				
				if (temp - prod < b)
					break;
					
				++ld;
			}
		}

		c[i] = ld;
		r = temp - b * c[i];
	}

	c.length = a.length;
	while (c.length > 0 && c[c.length - 1] == 0)
		--c.length;

	return c;
}

/*

BigInt BigInt::operator / (ShortType b) const;

void BigInt::Div(ShortType b, BigInt& quotient, ShortType& remainder);
void BigInt::Div(const BigInt& b, BigInt& quotient, BigInt& remainder);
*/

bool BigInt::operator < (const BigInt& b) const
{
	if (this->length < b.length)
		return true;
	else if (this->length > b.length)
		return false;

	for (int i = this->length - 1; i >= 0; --i)
		if (coeff[i] < b[i])
			return true;
		else if (coeff[i] > b[i])
			return false;

	return false;
}

bool BigInt::operator > (const BigInt& b) const
{
	return b < *this;
}

bool BigInt::operator <= (const BigInt& b) const
{
	return !(b < *this);
}

bool BigInt::operator >= (const BigInt& b) const
{
	return !(*this < b);
}
bool BigInt::operator == (const BigInt& b) const
{
	if (this->length != b.length)
		return false;

	for (int i = this->length - 1; i >= 0; --i)
		if (coeff[i] != b[i])
			return false;

	return true;
}

bool BigInt::operator != (const BigInt& b) const
{
	return !(*this == b);
}
